#include <iostream>
#include <set>
#include <iterator>
#include <algorithm>
#include <stdint.h>
#include <cassert>
#include <math.h>
#include <vector>

using namespace std;

//            10	          4
//           100                 25
//         1,000	        168
//        10,000	      1,229
//       100,000	      9,592
//     1,000,000	     78,498
//    10,000,000	    664,579
//   100,000,000	  5,761,455
// 1,000,000,000	 50,847,534

unsigned carmichael_[] = {
    561,     1105,     1729,     2465,     2821,
    6601,     8911,    10585,    15841,    29341,
    41041,    46657,    52633,    62745,    63973,
    75361,   101101,   115921,   126217,   162401,
    172081,   188461,   252601,   278545,   294409,
    314821,   334153,   340561,   399001,   410041,
    449065,   488881,   512461,   530881,   552721,
    656601,   658801,   670033,   748657,   825265,
    838201,   852841,   997633,  1024651,  1033669,
    1050985,  1082809,  1152271,  1193221,  1461241,
    1569457,  1615681,  1773289,  1857241,  1909001,
    2100901,  2113921,  2433601,  2455921,  2508013,
    2531845,  2628073,  2704801,  3057601,  3146221,
    3224065,  3581761,  3664585,  3828001,  4335241,
    4463641,  4767841,  4903921,  4909177,  5031181,
    5049001,  5148001,  5310721,  5444489,  5481451,
    5632705,  5968873,  6049681,  6054985,  6189121,
    6313681,  6733693,  6840001,  6868261,  7207201,
    7519441,  7995169,  8134561,  8341201,  8355841,
    8719309,  8719921,  8830801,  8927101,  9439201,
    9494101,  9582145,  9585541,  9613297,  9890881,
    10024561, 10267951, 10402561, 10606681, 10837321,
    10877581, 11119105, 11205601, 11921001, 11972017,
    12261061, 12262321, 12490201, 12945745, 13187665,
    13696033, 13992265, 14469841, 14676481, 14913991,
    15247621, 15403285, 15829633, 15888313, 16046641,
    16778881, 17098369, 17236801, 17316001, 17586361,
    17812081, 18162001, 18307381, 18900973, 19384289,
    19683001, 20964961, 21584305, 22665505, 23382529,
    25603201, 26280073, 26474581, 26719701, 26921089,
    26932081, 27062101, 27336673, 27402481, 28787185,
    29020321, 29111881, 31146661, 31405501, 31692805,
    32914441, 33302401, 33596641, 34196401, 34657141,
    34901461, 35571601, 35703361, 36121345, 36765901,
    37167361, 37280881, 37354465, 37964809, 38151361,
    38624041, 38637361, 39353665, 40160737, 40280065,
    40430401, 40622401, 40917241, 41298985, 41341321,
    41471521, 42490801, 43286881, 43331401, 43584481,
    43620409, 44238481, 45318561, 45877861, 45890209,
    46483633, 47006785, 48321001, 48628801, 49333201,
    50201089, 53245921, 53711113, 54767881, 55462177,
    56052361, 58489201, 60112885, 60957361, 62756641,
    64377991, 64774081, 65037817, 65241793, 67371265,
    67653433, 67902031, 67994641, 68154001, 69331969,
    70561921, 72108421, 72286501, 74165065, 75151441,
    75681541, 75765313, 76595761, 77826001, 78091201,
    78120001, 79411201, 79624621, 80282161, 80927821,
    81638401, 81926461, 82929001, 83099521, 83966401,
    84311569, 84350561, 84417985, 87318001, 88689601,
    90698401, 92625121, 93030145, 93614521, 93869665,
    94536001, 96895441, 99036001, 99830641, 99861985,
    100427041,101649241,101957401,102090781,104404861,
    104569501,104852881,105117481,105309289,105869401,
    106041937,107714881,109393201,109577161,111291181,
    114910489,115039081,115542505,116682721,118901521,
    119327041,120981601,121247281,122785741,124630273,
    127664461,128697361,129255841,129762001,130032865,
    130497361,132511681,133205761,133344793,133800661,
    134809921,134857801,135556345,136625941,139592101,
    139952671,140241361,144218341,145124785,146843929,
    150846961,151530401,151813201,153589801,153927961,
    157731841,158404141,158864833,159492061,161035057,
    161242705,161913961,163954561,167979421,168659569,
    169057801,169570801,170947105,171454321,171679561,
    172290241,172430401,172947529,173085121,174352641,
    175997185,176659201,178451857,178482151,178837201,
    180115489,181154701,182356993,184353001,186393481,
    186782401,187188001,188516329,188689501,189941761,
    193708801,193910977,194120389,194675041,196358977,
    200753281,206955841,208969201,212027401,213835861,
    214850881,214852609,216821881,221884001,225745345,
    226509361,227752993,228842209,230630401,230996949,
    231194965,237597361,238244041,238527745,241242001,
    242641153,246446929,247095361,250200721,252141121,
    255160621,256828321,257495641,258634741,266003101,
    270857521,271481329,271794601,273769921,274569601,
    275283401,277241401,278152381,279377281,280067761,
    280761481,288120421,289766701,289860481,291848401,
    292244833,292776121,295643089,295826581,296559361,
    299736181,300614161,301704985,302751505,306871201,
    311388337,318266641,321197185,321602401,325546585,
    328573477,329769721,333065305,333229141,334783585,
    338740417,346808881,348612265,354938221,357277921,
    357380101,358940737,360067201,362569201,364590721,
    366532321,366652201,367804801,367939585,368113411,
    382304161,382536001,390489121,392099401,393122521,
    393513121,393716701,395044651,395136505,396262945,
    399906001,403043257,403317421,405739681,413058601,
    413138881,413631505,416964241,417241045,419520241,
    426821473,429553345,434330401,434932961,438359041,
    440306461,440707345,455106601,458368201,461502097,
    461854261,462199681,471441001,471905281,473847121,
    477726145,481239361,483006889,484662529,490099681,
    490503601,492559141,496050841,499310197,503758801,
    507726901,509033161,510825601,511338241,516684961,
    517937581,518117041,518706721,527761081,529782121,
    530443201,532758241,533860309,540066241,542497201,
    544101481,545363281,545570641,547652161,548871961,
    549117205,549333121,549538081,551672221,552894301,
    555465601,556199281,556450777,557160241,557795161,
    558570961,558977761,561481921,561777121,564651361,
    568227241,569332177,573896881,577240273,579606301,
    580565233,590754385,593234929,595405201,597717121,
    600892993,602074585,602426161,602593441,606057985,
    609865201,611397865,612347905,612816751,616463809,
    618068881,620169409,621101185,625060801,625482001,
    629692801,631071001,633639097,638959321,642708001,
    652969351,656187001,662086041,672389641,683032801,
    683379841,684106401,686059921,689880801,697906561,
    698548201,702683101,703995733,704934361,705101761,
    707926801,710382401,710541481,711374401,713588401,
    717164449,721244161,722923201,727083001,739444021,
    743404663,744866305,745864945,746706961,752102401,
    759472561,765245881,771043201,775368901,775866001,
    776176261,781347841,784966297,790020001,790623289,
    794937601,798770161,804978721,809702401,809883361,
    814056001,822531841,824389441,824405041,829678141,
    832060801,833608321,834244501,834720601,836515681,
    839275921,841340521,842202361,843704401,847491361,
    849064321,851703301,851934601,852729121,854197345,
    855734401,860056705,863984881,867800701,868234081,
    876850801,882796321,885336481,888700681,891706861,
    897880321,902645857,914801665,918661501,928482241,
    930745621,931694401,934784929,935794081,939947009,
    940123801,941056273,945959365,947993761,954732853,
    955134181,957044881,958735681,958762729,958970545,
    962442001,962500561,963163201,963168193,968553181,
    968915521,975303121,977737321,977892241,981567505,
    981789337,985052881,986088961,990893569,993420289,
    993905641
};
static const unsigned carmichael_count = sizeof( carmichael_) / sizeof(carmichael_[0] );

unsigned modpow( uint64_t base, unsigned exponent, unsigned modulus ) {
    uint64_t result = 1;
    while ( exponent ) {
	if ( exponent & 1 ) {
	    result = ( result * base ) % modulus;
	}
	exponent >>= 1;
	base = ( base * base ) % modulus;
    }
    return result;
}

bool fermat_is_prime( const unsigned value ) {
    unsigned count = 8;
    if ( value == 1 ) return false;
    if ( value == 2 ) return true;
    if ( !(value & 1)) return false;

    if ( binary_search( &carmichael_[0], &carmichael_[0]+carmichael_count, value ) ) {
	return false;
    }
    while ( count-- ) {
	unsigned a = 1+lrand48()%(value-2);
	if ( 1 != modpow( a, value-1, value ) ) return false;
    }
    return true;
}


int main( int argc, char *argv[] ) {
    if ( argc == 2 ) {
	cout << "check prime" << endl;
	unsigned n( strtol( argv[1], NULL, 10 ) );
	cout << fermat_is_prime( n ) << endl;
    } else if ( argc == 3 ) {
	cout << "prime range" << endl;
	unsigned low( strtol( argv[1], NULL, 10 ) ), high( strtol( argv[2], NULL, 10 ) );
	for ( unsigned i = low; i <= high; i++ ) {
	    if ( fermat_is_prime(i) ) {
		cout << i << endl;
	    }
	}
    } else {
	unsigned count;
	cin >> count;
	while ( count-- ) {
	    unsigned low, high;
	    cin >> low >> high;
	    for ( unsigned i = low; i <= high; i++ ) {
		const bool prime(fermat_is_prime(i));
		if ( prime ) {
		    cout << i << endl;
		}
	    }
	    if ( count > 0 ) cout << endl;
	}
    }
    return 0;

}
